⟸ Go Back ⟸
Exercise 8 (Homework 4).
(decidable properties, context-free languages)

Some decidable properties of context-free languages

Let L_G be the (context-free) language produced by the context-free grammar G. Given as input the grammar G, describe an algorithm to decide whether

  1. L_G is empty.
  2. L_G is infinite.
  3. L_G contains some word of even length.
  4. L_G contains infinite words of even length.

What is the asymptotic cost of the algorithm proposed as a function of the number of symbols in G?

Important

Later in the course we will see that a lot of very natural questions on context-free grammar do not have an algorithm to decide them. Not that we didn’t find an algorithm yet. No algorithm exists that always terminate and gives the answer. For instance:

  • Given a context-free grammar, is it ambiguous?
  • Given a context-free grammar, does it describe a regular language?
  • Given a context-free grammar G with terminals \{a,b\}, is L_G=\{a,b\}^*?
  • Given two context-free grammars G_1 and G_2, is L_{G_1}\cap L_{G_2} empty?
  • Given two context-free grammars G_1 and G_2, is L_{G_1}= L_{G_2}?
  • Given two context-free grammars G_1 and G_2, is L_{G_1}\subseteq L_{G_2}?